1. Field of the Invention
The present invention relates to a viterbi decoding apparatus for use in the maximum-likelihood method for decoding convolution codes in, for example, satellite broadcasting.
2. Description of the Related Art
Viterbi decoding is known as one of methods for decoding convolution codes. The viterbi decoding is a decoding method that can achieve maximum likelihood decoding by processing a small amount of data.
FIG. 1 is a transition diagram (trellis diagram) that shows how convolution codes transfer if the constraint length applied is 4.
As FIG. 1 shows, a convolution code transfers from the transition state it assumes at a specific time, to a new, next transition state, when new information (1 bit) is input. (The transition state, also known as “state,” corresponds to the bit train that the memory elements of a convolution encoder stores at the specific time.) New information is either 0 or 1. Hence, the convolution code transfers to one of only two states from the transition state it assumes at the specific time. That is, there are only two paths through which the convolution code can transfer from one time point to another.
Of the two paths through which a convolution code transfers to any one of all possible transition states, the path having higher likelihood is selected in the viterbi decoding. To be more specific, two paths that are connected at a particular transition state are compared in terms of the Hamming distance (branch metric) between the signal received and the path and the cumulative sum (state metric) of branch metrics hitherto obtained. Then, of the two paths, the path having higher likelihood is selected for the transition state. The path thus selected is temporarily stored in a path memory circuit. This sequence of operations is repeated for a prescribed time (or performed at a plurality of times), and the results obtained are stored in the path memory circuit. That is, the path memory circuit stores the paths, each selected when the sequence of operations is performed. In the path memory circuit, the selected paths are traced, one after another, thereby finding two paths are more likely to be connected, than any other pair of paths. On the basis of the two paths thus found, the result of decoding is output.
The longer the time for which the selected paths are traced, the smaller the decoding error will be. However, the memory circuit has but a limited storage capacity, and the decoding apparatus used is limited in terms of computing ability. Inevitably, the path tracing is skipped for a specific period, and the decoding result is output. This specific period is called “cutoff period.”
In most cases, the hardware implementation of the path memory circuit is achieved by using a RAM, which stores the selected paths. The paths stored in the memory circuit are traced in a reversed-time direction. (See Jpn. Pat, Appln. Laid-Open Publication No. 2004-153319, Jpn. Pat, Appln. Laid-Open Publication No. 11-186920, and Jpn. Pat, Appln. Laid-Open Publication No. 2001-186026.) This method will hereinafter be referred to as trace-back method.
A trace-back method, in which a constraint length of 4 is applied in performing the path tracing, will be explained with reference to FIG. 2. Assume that the tracing is started at state 001. A convolution code in state 001 can transfer to states, i.e., state 000 and state 100. The path memory circuit stores 0 if a path leading to state 000 has been selected. It stores 1 (i.e., the most significant bit for the previous state) if a path leading to state 100 has been selected. The input is 1, whichever state the convolution code transfers from. This is expressed by the least significant bit for state 001. Thus, the tracing may be carried out as follows.
The least significant bit of the state being traced at present is used as decoding bit. The number of the state to be traced next is generated by adding, as new least significant bit, one of the bits stored in the path memory circuit, i.e., the most significant bit to the second least significant bit, all stored in the current trace state (see FIG. 3). The selected paths can therefore be traced back in sequence, starting with the state that assumes the minimum state metric.
To make the viterbi decoding apparatus operate at high speed, each RAM incorporated in the apparatus can be accessed only once during each clock cycle. How a path memory composed of, for example, four single-port memories operates in decoding a viterbi code by accessing each RAM only once will be explained below.
Assume that the constraint length of codes is set to 4 and cutoff period is set to 6. Four single-port RAMs are prepared, each having as many bits as states (8 bits in this case) and a number of words that corresponds to the cutoff period (6 words in this case). The path memory circuit receives as many selection data items as states, from a path-selecting circuit, during each clock cycle. The four RAMs switch the following four functions, from one to another, upon receiving clock pulses (6 pulses in this case) that correspond to the trace-skipping period, as is illustrated in FIG. 4.
(1) To write path-selection data items in sequence
(2) To trace the selected paths in accordance with the path-selection data items written, and not to decode codes
(3) To perform no accessing
(4) To perform tracing based on the result of function 2, i.e., tracing, and to output decoding bits
FIG. 5 is a diagram explaining how the RAMs operate when this memory operation is carried out.
The memory operation described above helps to constitute a viterbi decoding apparatus that can decode codes at high speed even if it used RAMs